﻿// 字符串全排列.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include<iostream>
#include<algorithm>
#include <vector>
#include <set>

using namespace std;
class Solution {
public:
	vector<string> permutation(string s) {
		dfs(s, 0);
		return res;
	}
private:
	vector<string> res;
	void dfs(string s, int x) {
		if (x == s.size() - 1) {
			res.push_back(s);                       // 添加排列方案
			return;
		}
		set<int> st;//用于去重
		for (int i = x; i < s.size(); i++) {
			if (st.find(s[i]) != st.end()) continue; // 重复，因此剪枝
			st.insert(s[i]);						//string在st中以ascall码表示
			swap(s[i], s[x]);                       // 交换，将 s[i] 固定在第 x 位
			dfs(s, x + 1);                          // 开启固定第 x + 1 位字符
			swap(s[i], s[x]);                       // 恢复交换
		}
	}
};
int main()
{
	//int ans[4] = { 8,2,3,4 };
	//sort(ans, ans + 4);    /* 这个sort可以不用，因为{1，2，3，4}已经排好序*/
	//do                             /*注意这步，如果是while循环，则需要提前输出*/
	//{
	//	for (int i = 0; i < 4; ++i)
	//		cout << ans[i] << " ";
	//	cout << endl;
	//} while (next_permutation(ans, ans + 4));
	Solution s;
	std::string str = "abcd";
	s.permutation(str);
	return 0;

}

